package 柠檬水找零;

/**
 * @author: AirMan
 * @date: 2025/4/24 14:27
 * @description:
 */
public class Solution {
    public boolean lemonadeChange(int[] bills) {
        // greedy
        // 局部最优：遇到账单20，优先消耗美元10，完成本次找零
        // 全局最优：完成全部账单的找零
        int fiveCnt = 0;
        int tenCnt = 0;
        for (int i = 0; i < bills.length; i++) {
            int bill = bills[i];
            switch (bill) {
                case 5:
                    fiveCnt++;
                    break;
                case 10:
                    if (fiveCnt != 0) {
                        fiveCnt--;
                        tenCnt++;
                        break;
                    } else {
                        return false;
                    }
                case 20:
                    if (tenCnt > 0 && fiveCnt > 0) {
                        tenCnt--;
                        fiveCnt--;
                    } else if (fiveCnt >= 3) {
                        fiveCnt -= 3;
                    } else {
                        return false;
                    }
                    break;
            }
        }
        return true;
    }
}
